package com.yanyuan.algorithm.sort;

/**
 * @Description 归并排序使用
 * 1、对数组进行分割
 * 2、递归调用方法
 * 3、归并原理使用
 * @Author yanyuan
 * @Date 13:34 2020/4/29
 * @Version 1.0
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] data = {23, 13, 26, 1, 2, 27, 38, 15};
        //data 待排数组，左下标，最右侧下标
        sort(data, 0, data.length - 1);
    }

    private static void sort(int[] data, int left, int right) {
        if(left >= right){
            return;
        }
        //找到拆分的中间索引(7/2=3,左边数据为4个)
        int center = (left + right) / 2;
        sort(data, left, center);
        sort(data, center + 1, right);
        //合并
        merge(data, left, center, right);
        for (int num: data){
            System.out.print(num + " ");
        }
    }

    /**
     *
     * @param data 待排序数组
     * @param left 左侧数组下标
     * @param center    右侧数组左下标
     * @param right 右侧数组最大值下标
     */
    private static void merge(int[] data, int left, int center, int right) {
        int[] tempArr = new int[data.length];
        int rightStart = center + 1;
        //记录临时下标
        int tempIndex = left;
        //缓存数组的第一个元素下标
        int  cacheIndex = left;

        while (left <= center && rightStart <= right){
            if(data[left] <= data[rightStart]){
                tempArr[tempIndex++] = data[left++];
            }else {
                tempArr[tempIndex++] = data[rightStart++];
            }
        }
        while (right <= right) tempArr[tempIndex++] = data[rightStart++];
        while (left <= center) tempArr[tempIndex++] = data[left++];

        //将临时数组中的元素拷贝回原始数据中
        while (cacheIndex <= right){
            data[cacheIndex] = tempArr[cacheIndex++];
        }
    }
}
